#导入生成范围内随机整数的库
from  random import randint

"""############################################
#####################(定义一个并查集)#########################"""
class Union_Find():
    def __init__(self,node_list):
        self.father=node_list
    def find(self,i):
        if(self.father[i]==i):#如果一个节点的父节点是其本身，那么该节点就是一个根节点
            return i
        self.father[i]=self.find(self.father[i])#路径压缩让i的父节点直接等于多次递归查询到的根节点，直接挂在根节点上
        return self.father[i]
    def is_in_same_set(self,u,v):#判断是否在同一个集合，这是并查集最重要的功能
        if(self.find(u)!=self.find(v)):######每调用一次find函数就执行了一次路径压缩
            #因此查询次数越多，查询的计算复杂度就从O(logN)越接近于O(1)
            return False
        return True
    #最需要注意的是join函数
    def join(self,u,v):
        f_u=self.find(u)#这样是不对的:father[v]=u
        #，在join函数中 我们需要寻找 u 和 v 的根，然后再进行连线在一起，而不是直接 用 u 和 v 连线在一起。
        f_v=self.find(v)#路径压缩
        if(f_u==f_v):#如果u,v在一个集合中,就不加入这个边
            return
        self.father[f_v]=f_u

"""############################################
#####################(定义一个并查集)#########################"""
#编写Prim算法
"""###################################
#构造带权的连通图
#   1.构造顶点集合V
#   2.构造边集合E
#   3.创建操作集合X和Y（X表示加入生成树点的集合，Y表示未加入生成树点的集合）
###################################"""
def Prim(V, E,X,Y):
    # 操作集合X和Y（X表示加入生成树点的集合，Y表示未加入生成树点的集合）
    min_wight_edge=10^3
    valid_edge=[]
    tree=[]
    wight=0
    while(len(tree)<len(V)-1):
        print(X, Y)
        for node in X:
            for v in Y:
                if(E[node][v]!=-1 and E[node][v]<min_wight_edge):
                    min_wight_edge=E[node][v]
                    valid_edge=[node,v]
        tree.append(valid_edge)
        wight+=min_wight_edge
        X.append(valid_edge[1])
        Y.pop(Y.index(valid_edge[1]))
        min_wight_edge=10^3#######################每次加入一个点到X集合后就要重置，否则会有问题
    return tree,wight

"""
#编写克鲁斯卡尔算法
#遍历所有的边构造一个小根堆
#优先选择权重最小的边
#判断边的两个节点是否在同一个集合（并查集）
#如果不在同一个集合，那么树加入这个边
"""
# https://blog.csdn.net/JohnJim0/article/details/109108875
def kruskal(V, E):
    valid_edge=[]
    tree=[]
    wight=0
    #遍历邻接矩阵，求出所有的边，以三元组的形式在小根堆中存储(权重,node1,node2)
    import heapq
    min_heap=[]
    for i in range(len(V)):
        for j in range(len(V)):
            if(i!=j and E[i][j]!=-1):
                heapq.heappush(min_heap,(E[i][j],i,j))
    #然后每次从堆顶弹出一个权重最小的边
    #初始化一个并查集
    union=Union_Find(list(range(len(V))))
    while(len(tree)<len(V)-1):
        rest_set=[]
        valid_edge=heapq.heappop(min_heap)
        while(union.is_in_same_set(valid_edge[1],valid_edge[2])):
            rest_set.append(valid_edge)
            valid_edge = heapq.heappop(min_heap)
        #终于找到了一条合理的边
        tree.append((valid_edge[1],valid_edge[2]))
        wight+=valid_edge[0]
        #并查集加入一个边
        union.join(valid_edge[1],valid_edge[2])
        #将前面弹出的边再放回去
        for e in rest_set:
            heapq.heappush(min_heap,e)
    return tree,wight


if __name__ == "__main__":
    # 1.构造顶点集合V
    V = ["A", "B", "C", "D", "E", "F"]
    # 2.构造边集合E
    E = [[0, 6, 1, 5, -1, -1],
         [6, 0, 5, -1, 3, -1],
         [1, 5, 0, 5, 6, 4],
         [5, -1, 5, 0, -1, 2],
         [-1, 3, 6, -1, 0, 6],
         [-1, -1, 4, 2, 6, 0]]
    # 3.创建操作集合X和Y
    X = [randint(0,len(V)-1)]
    Y=list(set(range(0,len(V)))-set(X))#差集
    #位运算符号类似
    #并集:|
    #交集:&
    #交集的补集:^
    print(Prim(V, E,X,Y))
    print(kruskal(V,E))



